//https://leetcode.cn/problems/add-two-numbers/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int len1 = 1;  //记录l1 l2的长度
        int len2 = 1;
        ListNode* p = l1;
        ListNode* q = l2;
        while(p->next != nullptr) {  //获取l1  l2 的长度
            len1++;
            p = p->next;
        }
        while(q->next != nullptr) {
            len2++;
            q = q->next;
        }
        if (len1 > len2) {   //l1  l2  哪个长的话在后面补零
            for (int i = 0; i < len1 - len2; i++) {
                q->next = new ListNode(0);
                q = q->next;
            }
        } else {
            for(int i = 0; i < len2 - len1; i ++) {
                p->next = new ListNode(0);
                p = p->next;
            }
        }
        p = l1;  //重新将链表首地址赋给  p  q
        q = l2;
        bool count = false;   //进位记录
        ListNode* l3 = new ListNode(-1);   //存放结果的链表
        ListNode* w = l3;      //l3 的移动指针
        int i = 0;  //记录相加的结果
        while (p != nullptr && q != nullptr) {   //逐位相加
            i = count + p->val + q->val;
            w->next = new ListNode(i % 10);
            count = (i >= 10) ? true : false;
            w = w->next;
            p = p->next;
            q = q->next;
        }
        if(count) {     //最后有进位需要开辟新的链表节点
            w->next = new ListNode(1);
            w = w->next;
        }
        return l3->next;
    }
};